package mo.tags.statecompress;

import java.util.HashMap;
import java.util.Map;

public class L464 {

    private Map<Integer, Boolean> memo = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((maxChoosableInteger+1)*maxChoosableInteger/2 < desiredTotal) {
            return false;
        }
        if (desiredTotal <= maxChoosableInteger) {
            return true;
        }
        return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    }


    private boolean dfs(int maxChoosableInteger, int useNumbers, int desiredTotal, int curTotals) {
        if (!memo.containsKey(useNumbers)) {
            boolean res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((useNumbers >> i) & 1) == 0) {
                    if (i+1+curTotals >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, useNumbers | (1 << i), desiredTotal, curTotals+i+1)) {
                        res = true;
                        break;
                    }
                }
            }
            memo.put(useNumbers, res);
        }

        return memo.get(useNumbers);
    }

}
